package net.dodoman.sort;

public class Sorter {
	// 程序中的通用方法：
	/**
	 * 交换方法,把数组中的第i个数和第j个数进行交换。
	 * 
	 * @param array
	 * @param i
	 * @param j
	 * @return boolean 交换成功返回true，否则返回false。
	 */
	public static boolean swap(int array[], int i, int j) {
		if (i >= array.length || j >= array.length) {
			return false;
		}
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
		return true;
	}

	// 测试用数据：
	// 6,5,8,3,9,1,4,2,7,0

	/**
	 * (1) 选择排序:
	 * 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后
	 * ，前i个记录的位置已经是正确的了。
	 **/
	/**
	 * 选择排序法
	 * 
	 * @param vec
	 *            要排序的数组
	 */
	public static void sortSelection(int[] vec) {
		for (int i = 0; i < vec.length; i++) {
			for (int j = i; j < vec.length; j++) {
				if (vec[j] < vec[i]) {
					swap(vec, i, j);
				}
			}
		}
	}

	/**
	 * (3) 插入排序
	 * 插入排序算法策略：排序值列中的前2个值，并在必要时交换它们。在相对于前2个值（有序的）的适当位置插入值列的第三个值。然后，在相对于前3个值
	 * （有序的）的适当位置插入值列的第4个值。每进行一次插入操作，有序子集中的数值个数将递增1。重复该过程，直至值列中的所有值都按照次序排列为止。
	 * 插入过程需要移动数组中的其他值，为插入的元素腾出存储空间。
	 **/

	/**
	 * 插入排序法
	 * 
	 * @param data
	 */
	@SuppressWarnings("unchecked")
	public static void insertionSort(Comparable[] data) {
		for (int index = 1; index < data.length; index++) {

			Comparable key = data[index];
			int position = index;
			// shift larger values to the right
			while (position > 0 && data[position - 1].compareTo(key) > 0) {
				data[position] = data[position - 1];
				position--;
			}
			data[position] = key;
		}
	}
}
